package Algorithm.dfs;

/**
 * 463. 岛屿的周长 https://leetcode.cn/problems/island-perimeter
 * 题目简述：长方形海洋网格中只有一座岛屿，求其周长
 */
public class IslandPerimeter {

    public static void main(String[] args) {
        new IslandPerimeter().islandPerimeter(new int[][]{
                {0,1,0,0},
                {1,1,1,0},
                {0,1,0,0},
                {1,1,0,0}});
    }

    /**
     * 岛屿系列问题3
     * dfs解法
     */
    int perimeter = 0;
    public int islandPerimeter(int[][] grid) {
        for(int i = 0;i < grid.length;i++) {
            for(int j = 0;j < grid[0].length;j++) {
                //题设只有一座岛屿，故遍历到岛屿后，直接用dfs遍历整个岛屿，统计每个岛屿网格的外部边长
                if(grid[i][j] == 1) {
                    dfs(i, j, grid);
                    return perimeter;
                }
            }
        }
        return perimeter;
    }

    /**
     * dfs遍历一座岛屿，dfs函数返回的是[i][j]网格是否为海洋，超出数组边界的也是海洋
     */
    public int dfs(int i, int j, int[][] grid) {
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length)
            return 1;
        if(grid[i][j] == 0)
            return 1;
        if (grid[i][j] == 2)
            return 0;
        grid[i][j] = 2;
        int up = dfs(i-1, j, grid);
        int down = dfs(i+1, j, grid);
        int left = dfs(i, j-1, grid);
        int right = dfs(i, j+1, grid);
        //一个岛屿网格的外部边长即为其周围的海洋格数
        perimeter += up + left + down + right;
        return 0;
    }
}
